1. Field of the Invention
The present invention relates to a quantum public key encryption system, a key generation apparatus, an encryption apparatus, a decryption apparatus, a key generation method, an encryption method, and a decryption method.
2. Description of the Related Art
With a rapid development of information processing technology and communication technology, digitisation of document, regardless of official or private, is rapidly advancing. Accordingly, many individuals and companies are greatly interested in secure management of electronic documents. With the increase in the interest, security against tampering, such as eavesdropping and forgery, are being hotly debated in many fields. The security against eavesdropping on an electronic document is ensured by encrypting the electronic document, for example. Also, the security against forgery of an electronic document is ensured by using a digital signature, for example. However, encryption and the digital signature have to be sufficiently tamper-resistant.
Public key encryption that is currently widely used takes computational complexity of a classical computer as a basis for security. For example, RSA encryption takes “difficulty of prime factorisation of a large composite number (hereinafter, prime factorisation problem)” as a basis for security. Also, DSA encryption and ElGamal encryption take “difficulty of solving discrete logarithm problem” as a basis for security. However, a quantum computer is said to be capable of efficiently computing solutions to the prime factorisation problem and the discrete logarithm problem. That is, the security of the encryption described above that is currently widely used is not guaranteed once the quantum computer is realised.
Additionally, the expression “classical” is used in a sense that it is not “quantum.” Also, the expression “quantum” means basing on a principle of quantum mechanics or application of the principle of quantum mechanics. For example, the quantum computer is a calculator adopting a superposition principle of quantum mechanics. Also, a quantum key distribution scheme such as BB84 uses an uncertainty principle of quantum mechanics.
Against the background of such circumstances, researches on public key cryptosystem that guarantees security even if the quantum computer is realised are actively conducted. One direction of the researches is to realise public key cryptosystem in a classical communication channel by taking, as a basis for security, a problem that is difficult to efficiently calculate (for example, difficulty of solving a multivariable polynomial) even when using the quantum computer. Also, another direction is to realise a quantum public key cryptosystem that guarantees security against an attack using the quantum computer, by using a quantum communication channel and quantum computation. For example, T. Okamoto, K. Tanaka, S. Uchiyama, “Quantum Public Key Cryptosystems”, Proc. of CRYTPTO 2000, LNCS 1880, pp. 147-pp. 165, Springer-Verlag (2000), Japan Patent No. 3615132 and JP-A-2008-294666 disclose examples of findings of the researches relating to the quantum public key cryptosystem.
The quantum public key cryptosystems disclosed by Okamoto et al. and Japan Patent No. 3615132 take computational complexity of a subset sum problem, which is a special case of a knapsack problem, as a basis for security. This subset sum problem is a problem of determining “whether a subset can be appropriately selected from given n integers a1, . . . , an and the sum of numbers belonging to the subset can be made equal to a given number N.” This subset sum problem belongs to a computational class NP-complete. However, it is not self-evident whether it is extremely difficult to solve the subset sum problem by using the quantum computer. Accordingly, it is difficult to say that the quantum public key cryptosystems disclosed by Okamoto et al. and Japan Patent No. 3615132 are absolutely safe against an attack using the quantum computer.
Furthermore, the quantum public key cryptosystem disclosed by Japan Patent No. 3615132 uses a quantum state as a public key. Therefore, when using the quantum public key cryptosystem disclosed by Japan Patent No. 3615132, an issue as follows arises. Normally, a public key used by a public key cryptosystem is certified by a certificate authority. If a public key is information that is classically described (hereinafter, classical information), whether the public key is definitely certified by the certificate authority or not can be verified. However, it is not self-evident whether it is possible to verify certification/non-certification of a public key represented by the quantum state (hereinafter, quantum public key). For example, the quantum state changes by measurement, and thus, when verifying certification/non-certification of a quantum public key, there is a possibility that the quantum public key becomes useless as a public key.
On the other hand, a quantum public key cryptosystem disclosed by JP-A-2008-294666 uses a hybrid-type public key (hereinafter, hybrid public key) that combines the quantum state and the classical information. The hybrid public key includes a classical information part. Thus, by performing authentication by using the classical information part and verifying certification/non-certification by using the classical information part, verification of certification/non-certification is enabled without disturbing the quantum state. Of course, verification is not performed on the quantum state. However, if the quantum state is altered in some way, there will be an inconsistency with the verified classical information, and thus, encryption using the hybrid public key or decryption using a private key will fail. Accordingly, in reality, not performing verification on the quantum state will not be an issue.